#ifndef DATA_STRUCTURE_BSTREE_H
#define DATA_STRUCTURE_BSTREE_H

#include<iostream>

using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct {
    KeyType key;
    InfoType otherinfo;
} ElemType;
typedef struct BSTNode {
    ElemType data;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

BSTree SearchBST(BSTree T, KeyType key, int &a) {
    a++;
    if ((!T) || key == T->data.key) return T;
    else if (key < T->data.key) return SearchBST(T->lchild, key, a);
    else return SearchBST(T->rchild, key, a);
}

void InsertBST(BSTree &T, ElemType e) {
    if (!T) {
        BSTNode *S = new BSTNode;
        S->data = e;
        S->lchild = S->rchild = NULL;
        T = S;
    } else if (e.key < T->data.key)
        InsertBST(T->lchild, e);
    else if (e.key > T->data.key)
        InsertBST(T->rchild, e);
}

void CreatBST(BSTree &T) {
    T = NULL;
    ElemType e;
    cout << "输入个数，最小值，最大值:";
    int n, min, max;
    cin >> n >> min >> max;
    for (int i = 0; i < n; ++i) {
        e.key = rand() % (max - min + 1) + min;
        InsertBST(T, e);
    }

}

void DeleteBST(BSTree &T, KeyType key) {
    BSTNode *p;
    BSTNode *f;
    p = T;
    f = NULL;
    while (p) {
        if (p->data.key == key) break;
        f = p;
        if (p->data.key > key) p = p->lchild;
        else p = p->rchild;
    }
    if (!p) return;
    BSTNode *q;
    q = p;
    if ((p->lchild) && (p->rchild)) {
        BSTNode *s;
        s = p->lchild;
        while (s->rchild) {
            q = s;
            s = s->rchild;
        }
        p->data = s->data;
        if (q != p) q->rchild = s->lchild;
        else q->lchild = s->lchild;
        delete s;
        return;
    } else if (!p->rchild)
        p = p->lchild;
    else if (!p->lchild)
        p = p->rchild;
    if (!f) T = p;
    else if (q == f->lchild) f->lchild = p;
    else f->rchild = p;
    delete q;
}

void InorderTree(BSTree T) {
    if (T) {
        InorderTree(T->lchild);
        cout << T->data.key << " ";
        InorderTree(T->rchild);
    }
}

#endif //DATA_STRUCTURE_BSTREE_H
